package com.arithmetic.basics;

import java.util.*;

/**
 * 有效的括号
 * 1.问题描述
 * 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 示例 4：
 * 输入：s = "([)]"
 * 输出：false
 * 示例 5：
 * 输入：s = "{[]}"
 * 输出：true
 * 3.提示
 * 1 <= s.length <= 10^4
 * s 仅由括号 ‘()[]{}’ 组成
 * 4.具体解法（栈加哈希表判断，栈加直接判断，栈加ASCII值判断，repalce方法解决）
 */
public class Day2 {
    public static void main(String[] args) {
        Day2 day2 = new Day2();
        day2.isValid("[3333333333333333333333]");
    }


    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) { // 因为需要匹配的字符是偶数，所以如果字符串长度是奇数，那肯定是不能匹配的
            return false;
        }
        Map<Character, Character> pairs = new HashMap<>(); // 使用hashmap来储存每一种符号，其中，键是右符号，值是左符号
        pairs.put('}', '{');
        pairs.put(']', '[');
        pairs.put(')', '('); //  //将括号存储好后，就可以将字符串进栈进行判断了;字符串每个字符依次进栈，只要遇到左括号就入栈
        //遇到右括号就从栈中取出一个进行匹配（用哈希表），依次类推，直到字符串遍历完毕，栈中无括号，则是有效的
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //charAt(i),返回字符串指定索引处的char值，序列的第一个char值是索引0 ，下一个索引为1 ，一次类推，像数组索引一样
            char ch = s.charAt(i);
            //containsKey的作用是判断哈希表中是不是有这个键（也就是右括号），如果有，说明此时判断的字符是右括号
            if (pairs.containsKey(ch)) {
                //peek()方法是只查看，不从栈中取出
                //pop()是查看并从栈中取出
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;//已知是右括号了（因为有这个键），如果此时栈是空的，或者对应的左括号不匹配就说明不匹配
                } else {
                    stack.pop();//如果不属于前面的情况，那说明右括号和左括号匹配上了，那么将栈中的左括号拿出来即可
                }
            } else {
                stack.push(ch);//如果通过containsKey发现不存在这个键，那么说明是左括号，那么就应该入栈
            }
        }
        return stack.isEmpty();//字符串全遍历完毕了，如果栈是空的那么就是匹配好了，如非空，就没匹配好。所以用isEmpty就正好对应了这个返回值的需求
    }


    //方法二：是使用了栈而没用哈希表的一种方法，效率优于使用哈希表
    //直接就是用获得的字符进行判断，省空间，时间复杂度是一样的
    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();//这个就是用Stack类创建的栈，而不是用Deque
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }//如果是左括号，那么push进栈
            else if (stack.isEmpty() || c == ')' && stack.pop() != '(' || c == ']' && stack.pop() != '[' || c == '}' && stack.pop() != '{') {
                //如果不是左括号，那么说明是右括号
                //此时如果栈是空的，或者此时判断的右括号是），而栈顶的元素不是（，或者}{][不能匹配到，那么就输出false
                return false;
            }
        }
        return stack.isEmpty();
    }


    //方法三：使用replace方法的巧妙思路，效率低，但是代码很短小精悍
    //replace(s1,s2),用s2串去替换所有的s1串
    public boolean isValid3(String s) {
        while (true) {
            int len = s.length();
            s = s.replace("()", "");//用空字符替换匹配的括号
            s = s.replace("{}", "");
            s = s.replace("[]", "");
            //执行完一轮之后，如果长度变了，说明有匹配的，所以返回去再做赋值和匹配。
            //如果没变，那说明没有一组可以匹配的了，此时判断字符串的长度是不是0，如果是0，那么会返回true
            if (s.length() == len) {
                return len == 0;
            }
        }
    }

    //方法四：使用ASCII加字节数组进行判断
    //其实就是将字符类型通过数字来进行判断了，而转换的途径就是ASCII
    //而且，匹配的括号应该相差的ASCII值是1或者2，由此可以进行括号是否匹配的判断
    public boolean isValid4(String s) {
        byte[] s_byte = s.getBytes();//字符串转化为byte数组，即对应字符的ASCII码表。
        Stack<Byte> stack = new Stack<>();//创建栈。
        byte symbol = 0;//这个目标一直是栈顶的那个元素，等待被消除
        if (s.length() % 2 != 0) {
            return false;  //奇数个字符直接返回false。
        }
        for (int i = 0; i < s.length(); i++) {
            if (s_byte[i] == 40 || s_byte[i] == 91 || s_byte[i] == 123) {
                //下一个字符为(、{、[之一时，压栈。
                stack.push(s_byte[i]);//被消除者为(、{、[ ，将这些字符压入栈中。
                symbol = s_byte[i];  //修改消除目标为当前最新压入的被消除者。
            } else if (s_byte[i] == (symbol + 1) || s_byte[i] == (symbol + 2)) {
                //下一个字符为 )、}、]之一时，弹栈。
                stack.pop();
                symbol = stack.empty() ? 0 : stack.peek(); //消除成功，更换新的消除目标。
            } else {
                return false;
            }
        }
        while (stack.empty()) {  //结束且栈中无剩余。
            return true;
        }
        return false;   //栈中有剩余。
    }


    //解法五：ASCII值加字符数组
    //类似于方法四，只不过更简洁一点，采用的s.toCharArray()将s变成字符数组进行判断，而方法四是变成字节数组
    public boolean isValid5(String s) {
        if (s.isEmpty()) return true;//if的代码块只有一句，可以不加大括号
        //一种全新的判断是不是偶数的方式，跟1按位与，结果是1则为奇数，底层逻辑应该是二进制
        if ((s.length() & 1) == 1) return false;
        //发现这几种方法中，创建栈的方式各种各样，都可以，新手不要拘束，各自优点可以以后慢慢了解
        Deque<Character> stack = new ArrayDeque<>();
        //s.toCharArray()是将串s变成字符数组
        for (char ch : s.toCharArray()) {
            // '('，')'，'{'，'}'，'['，']' 的 ASCII 码分别是 40、41、91、93、123、125
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (stack.isEmpty() || Math.abs(ch - stack.pop()) > 2) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
